The present invention relates to an arithmetic unit for inverse trigonometric function utilized in a computer.
Calculation of the inverse trigonometric function is one of the necessary features for computers of the type carrying out scientific and technological computation. The calculation methods of the inverse trigonometric function include a method utilizing Taylor series expansion: EQU arctan x=x-x.sup.3 /3+x.sup.5 /5-x.sup.7 /7 (1)
and a method according to meromorphic function approximation using continued fraction expansion or Tchebycheff series expansion. However, these methods have drawbacks that they need a relatively long calculation time due to frequent repetition of multiplication and division and they do not provide a sufficient calculation precision.
Further, there is another calculation method for inverse trigonometric function of Cordinate Rotational Digital Computer (hereinafter, referred to as "CORDIC") which is suitable for micro-program-controlled computer. Since the CORDIC method can be carried out by adding operation, subtracting operation and right-shifting operation, this method is efficient for use in computers which have no fast multiplier unit.
Arithmetic principle of the CORDIC method is explained hereinafter for calculating an inverse trigonometric function .theta.=arctan (y/x) according to binary notation with the precision of n bits. In this method, the angle value .theta. is represented as follows by using constants .gamma..sub.k and a series {a.sub.k }: EQU .theta.=a.sub.o .times..gamma..sub.o +a.sub.1 .times..gamma..sub.1 +a.sub.2 .times..gamma..sub.2 + . . . +a.sub.n-1 .times..gamma..sub.n-1 +.epsilon.(2)
where, EQU .gamma..sub.k =arctan(2.sup.-k) (3) EQU a.sub.k ={+1,-1} (4)
In this method, determination of the series }a.sub.k } from the input values x and y is called pseudo division, and determination of the angle value .theta. from the series }a.sub.k } is called pseudo multiplication.
In order to determine the series {a.sub.k }, the input value x is expressed by x=R.times.cos .theta. and the input value y is expressed by Y=R.times.sin .theta. where R=x.sup.2 +y.sup.2, and the addition theorem is applied.
If cos(.phi..sub.k).gtoreq.0, EQU a.sub.k =+1 (5) EQU .phi..sub.k+1 =.phi..sub.k +.gamma..sub.k ( 6) EQU cos(.phi..sub.k+1)=R'.sub.k (cos .phi..sub.k -2.sup.-k .times.sin .phi..sub.k) (7) EQU sin(.phi..sub.k+1)=R'.sub.k (sin .phi..sub.k +2.sup.-k .times.cos .phi..sub.k) (8)
If cos(.phi..sub.k)&lt;0, EQU a.sub.k =-1 (9) EQU .phi..sub.k+1 =.phi..sub.k -.phi..sub.k ( 10) EQU cos(.phi..sub.k+1)=R'.sub.k (cos .phi..sub.k +2.sup.-k .times.sin .phi..sub.k) (11) EQU sin(.phi..sub.k+1)=R'.sub.k (sin .phi..sub.K -2.sup.-k .times.cos .phi..sub.k) (12)
where EQU R'.sub.k =1/R.sub.k (13)
By repeatedly carrying out the above-described arithmetic steps for sequence number k=0, . . . n-1, the value of cos(.phi..sub.K) approaches to zero, thereby obtaining the value of arctan (y/x). In these operation steps, the arithmetic relations (7), (8), (11) and (12) represent the pseudo division for determining the series {a.sub.k }, and the arithmetic relations (6) and (10) represent the pseudo multiplication for determining the value .theta. from the series {a.sub.k }.
The algorithm of CORDIC method applied to the above-described steps is represented as follows.
1. The arithmetic unit is set with initial values x.sub.o =x, y.sub.o =y and v.sub.o =0 (0.ltoreq.y&lt;x&lt;.infin.).
2. The following step 3 is repeatedly carried out for the sequence number k=0, 1, 2, . . . , n-1.
3. If y.sub.k .gtoreq.0, a.sub.k is set to a.sub.k =+1, and if y.sub.k &lt;0, a.sub.k is set to a.sub.k =-1. Then, the following calculations are carried out: EQU x.sub.k+1 =x.sub.k +a.sub.k .times.2.sup.-k .times.y.sub.k (14) EQU y.sub.k+1 =y.sub.k -a.sub.k .times.2.sup.-k .times.x.sub.k ( 15) EQU v.sub.k+1 =v.sub.k +a.sub.k .times..gamma..sub.k ( 16)
where .gamma..sub.k is the constant value satisfying the relation (3).
4. Lastly, the value .theta.=arctan (y/x) is obtained as the final value of v.sub.n.
The conventional algorithm of CORDIC method is carried out according to a flow chart shown in FIG. 4 by utilizing an arithmetic unit shown in FIG. 2 which has two barrel shifters and three adder-subtracters. Referring to FIG. 2, the conventional arithmetic unit includes three registers 211, 221 and 231 for storing the binary variables y.sub.k, x.sub.k and v.sub.k, respectively, two barrel shifters 213 and 223 for right-shifting the contents of registers 221 and 211 by a given shift bit count, respectively, an n-word ROM 204 for storing and outputting the constant values .gamma..sub.k defined by the relation (3), a first adder-subtracter 212 for selectively adding and subtracting the content of barrel shifter 213 to and from the content of register 211, a second adder-subtracter 222 for selectively adding and subtracting the content of barrel shifter 223 to and from the content of register 221, a third adder-subtracter for selectively adding and subtracting the content of ROM 204 to and from the content of register 231, and a counter 205 for designating the shift bit count k of the barrel shifter 213 and 223 and for designating the address number k of ROM 204.
Next, the operation of arithmetic unit shown in FIG. 2 is explained according to the algorithm of conventional CORDIC method shown in FIG. 4.
1. The registers 211, 221 and 231 are set with the initial values y.sub.o =y, x.sub.o =x and v.sub.o =0, respectively (steps 402, 401, and 403).
2. The following procedure 3 is repeated with increment of the content k of counter 205 from k=0 to k=n-1 (step 409).
3. For the specific sequence number k, the register 211 is stored with the variable y.sub.k according to the relation (15), the register 221 is stored with the variable x.sub.k according to the relation (14), the register 231 is stored with the variable v.sub.k according to the relation (16), and the counter 205 stores the current sequence number k. The barrel shifter 213 operates to right-shift the content of register 221 by the shift bit count k indicated by the counter 205 to thereby multiply the content by factor 2.sup.-k, and the barrel shifter 223 operates to right-shift the content of register 211 by the shift bit count k indicated by the counter 205 to thereby multiply the content by factor 2.sup.-k.
In step 406, if the value of sign bit of the content y.sub.k stored in the register 211 is positive, the value of a.sub.k is determined to a.sub.k =+1. Consequently, the adder-subtracter 212 carries out the subtracting operation to update the variable y.sub.k+1 =y.sub.k -(2.sup.-k)x.sub.k (step 412), the adder-subtracter 222 carries out the adding operation to update the variable x.sub.k+1 =X.sub.k +(2.sup.-k)Y.sub.k (step 411), and the adder-subtracter 232 carries out the adding operation to update the variable v.sub.k+1 =v.sub.k +.gamma..sub.k (step 413).
On the other hand, if the value of sign bit of the content y.sub.k stored in the register 211 is negative, the value a.sub.k is determined to a.sub.k =-1. Consequently, the adder-subtracter 212 carries out the adding operation to update the variable Y.sub.k+1 =Y.sub.k +(2.sup.-k)x.sub.k (step 422), the adder-subtracter 222 carries out the subtracting operation to update the variable X.sub.k +1=X.sub.k -(2.sup.-k)Y.sub.k (step 421) and the adder-subtracter 232 carries out the subtracting operation to update the variable v.sub.k+1 =v.sub.k .gamma..sub.k (step 423). The outputs of three adder-subtracters 212, 222 and 232 are stored in the corresponding registers 211, 221 and 231 as the updated variables y.sub.k+1, x.sub.k+1 and v.sub.k+1, respectively.
4. After repeating the above-described procedure 3 n times from k=0 to k=n-1 (step 409), the register 231 is stored with the final variable v.sub.n which determines the value of arctan (y/x)=v.sub.n (step 410). According to the above-described operation, if the procedure 3 requires one clock for each time to process, the total calculating process requires about n number of clocks.
FIG. 3 shows another conventional arithmetic unit having a single barrel shifter and a single adder-subtracter for effecting the algorithm of CORDIC method.
Referring to FIG. 3, the arithmetic unit comprises three registers 308, 307 and 309 for storing three kinds of binary variables y.sub.k, x.sub.k and v.sub.k, respectively, a barrel shifter 303 for carring out selectively right-shifting and left-shifting of binary values by a given shift bit count, an n-word ROM 302 for generating the constant values .gamma..sub.k defined by the relation (3), and an adder-subtracter 304 for selectively adding or subtracting contents of a pair of input ports A and B thereof to each other or from each other. A counter 306 operates to control a cycle number of the CORDIC loop procedure, and another counter 301 designates the shift bit count k of the barrel shifter 303 and the address number k of the ROM 302.
Next, the operation of arithmetic unit shown in FIG. 3, is explained according to the algorithm of CORDIC method shown in FIG. 4.
1. The registers 307, 308 and 309 are set with the initial values x.sub.o =x, y.sub.o =y and v.sub.o =0, respectively (steps 401, 402 and 403), the counter 301 is set with the initial sequence number k=0 (step 405) and the counter 306 is set with the initial value n=number of bits (step 404).
2. The following procedure 3 is repeatedly carried out for n times with decrement of the content of counter 306 from n to 1.
3. The register 308 is stored with the current variable y.sub.k according to the relation (15), the register 307 is stored with the current variable x.sub.k according to the relation (14), the register 309 is stored with the current variable v.sub.k according to the relation (16), and the counter 301 is stored with the current sequence number k. The barrel shifter 303 operates to right-shift a binary value outputted from a data bus by the given shift bit count k indicated by the counter 301 to thereby multiply the outputted binary value by the factor 2.sup.-k.
If the sign bit of the content of register 305 indicates positive (step 306), the value of series component a.sub.k is determined to a.sub.k =+1. At this stage, the content x.sub.k of register 307 is transferred to the input port A, and the content y.sub.k of register 308 is transferred to the barrel shifter 303 in which the variable y.sub.k is right-shifted with the shift bit count k indicated by the counter 301 and the right-shifted value (2.sup.-k)y.sub.k is transferred to the other input port B. Then the adder-subtracter 304 carries out the adding operation between the input ports A and B, and the result is transferred to the register 307 (step 411). Next, the content y.sub.k of register 308 is transferred to the input port A, and the content x.sub.k of register 307 is right-shifted by the barrel shifter 303 with the shift bit count k designated by the counter 301 and the right-shifted value is transferred to the other input port B. Then, the adder-subtracter carries out the subtracting operation between the input ports A and B and the calculated result is transferred to the register 308 (step 412). Next, the content v.sub.k of register 309 is transferred to the input port A, and the content of the ROM 303 addressed by the sequence number k which is indicated by the counter 301 is transferred to the other input port B. Then, the adder-subtracter 304 carries out the adding operation between the input ports A and B and the calculated result is transferred to the register 309 (step 413).
On the other hand, if the sign bit of the content of register 305 indicates negative, the value of series component a.sub.k is determined to a.sub.k =-1. At this time, the content x.sub.k of register 307 is transferred to the input port A, and the content y.sub.k of register 308 is right-shifted by the barrel shifter 303 with the shift bit count k indicated by the counter 301 and the right-shifted value 2.sup.-k .times.y.sub.k is transferred to the other input port B. Then the adder-subtracter 304 carries out the subtracting operation between the input ports A and B, and the result is transferred to the register 307 (step 421). Next, the content y.sub.k of register 308 is transferred to the input port A, and the content x.sub.k of register 307 is right-shifted by the barrel shifter 303 with the shift bit count k designated by the counter 301 and the right-shifted value is transferred to the other input port B. Then, the adder-subtracter 304 carries out the adding operation between the input ports A and B and the calculated result is transferred to the register 308 (step 422). Next, the content v.sub.k of register 309 is transferred to the input port A, and the content of the ROM 303 addressed by the sequence number k which is indicated by the counter 301 is transferred to the other input port B. Then, the adder-subtracter 304 carries out the subtracting operation between the input ports A and B and the calculated result is transferred to the register 309 (step 413).
4. The above-described procedure 3 is repeated n times (step 409), and thereafter the register 309 is stored with the final value v.sub.n =arctan (y/x) (step 410).
The above-described conventional procedure is carried out by micro program. In such micro program, if the above-described procedure 3 requires .alpha. number of clocks for each time, the total calculating procedure requires n.times..alpha. number of clocks and therefore a considerably long calculation time.
The forementioned two types of conventional arithmetic units for inverse trigonometric function have the following drawbacks.
With respect to the conventional unit of FIG. 2, firstly, the unit requires many hardware elements including two barrel shifters and three adder-subtracters. If the unit is incorporated into a large scale integrated circuit (LSI), since the barrel shifter occupies a large area, the total area assigned to the arithmetic unit for inverse trigonometric function becomes great. Especially in order to carry out the highly precise calculation (with multi length word), both of the barrel shifter and adder-subtracter need a larger area within the LSI. In addition, since the conventional arithmetic unit cannot be utilized for general purpose other than for calculation of the inverse trigonometric function, the cost performance is not satisfactory. Secondly, the precision of calculation result is not good. Namely, since the constant value .gamma..sub.k defined by the relation (3) becomes small in accordance with the increment of sequence number k, significant figure of the constant value .gamma..sub.k is decreased and the rounding error is accumulated about the least significant bit (LSB). Further, since calculation of the relations (7), (8), (11) and (12) is based on the algorithm with fixed point number, if the variable x, y and arctan (y/x) are represented by floating point number, the variables x and y have to be converted into the fixed point number so as to calculate the value of arctan (y/x) and then the value of arctan (y/x) of the fixed point number has to be converted into the floating point number. In such case, if the variable x or y has a very small value, the significant figures are considerably reduced through the conversion into the fixed point number.
With respect to the other conventional unit of FIG. 3, it has a drawback that the calculation time is considerably long. Since the process of CORDIC method (relating to the arithmetic relations (6), (7), (8), (10), (11) and (12)) is carried out entirely by micro program, a considerably long calculation time is needed.